/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-02-07 20:35:54
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-02-07 20:45:46
 * @FilePath: \LeetCode\52.n-皇后-ii.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=52 lang=cpp
 *
 * [52] N 皇后 II
 */

#include <cstdlib>
#include <algorithm>

// @lc code=start
class Solution
{
public:
    int result = 0;                                  // 不同的解决方案的数量
    int chessBoard[9] = {0, 1, 2, 3, 4, 5, 6, 7, 8}; // 每行皇后的位置 0 ~ n-1
    int m_n;

    inline bool judge(int i) // i: 当前放置皇后棋子的位置
    {
        for (int j = 0; j < i; j++)
        {
            /* 不在同一斜线上 */
            if (std::abs(i - j) == std::abs(chessBoard[i] - chessBoard[j]))
                return false;
        }
        return true;
    }

    void sortTreeDFS(int i)
    {
        if (i == m_n)
        {
            result++;
            return;
        }

        for (int k = i; k < m_n; k++)
        {
            std::swap(chessBoard[i], chessBoard[k]);
            if (judge(i)) // 交换有效
            {
                sortTreeDFS(i + 1);
            }
            std::swap(chessBoard[i], chessBoard[k]);
        }
    }

    int totalNQueens(int n)
    {
        m_n = n;
        sortTreeDFS(0);
        return result;
    }
};
// @lc code=end
